package top.houry.sort;

import java.util.Date;

/**
 * @Desc
 * @Author houruiyang
 * @Date 2022/9/28
 **/
public class MergeSort {
    public static void main(String[] args) {
        int[] array = new int[10];
        for (int i = 0; i < array.length; i++) {
            array[i] = (int) (Math.random() * 100);
            System.out.print(array[i] + ",");
        }

        System.out.println();
        mergeSort(array);

        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ",");
        }

    }

    public static void mergeSort(int[] array) {
        int[] temp = new int[array.length];
        mergeSortImpl(array, 0, array.length -1, temp);
    }

    public static void mergeSortImpl(int[] array, int start, int end, int[] temp) {



        if (start >= end) {
            return;
        }


        int mid = start + (end - start) / 2;
        mergeSortImpl(array, start, mid, temp);

        System.out.println("-----");

        mergeSortImpl(array, mid+1, end, temp);

        merge(array, start, mid, end, temp);





    }

    public static void merge(int[] array, int start, int mid,int end, int[] temp) {
        int left = start;
        int right = mid + 1;
        int index = start;
        while (left <= mid && right <= end) {
            if (array[left] < array[right]) {
                temp[index++] = array[left++];
            } else {
                temp[index++] = array[right++];
            }
        }
        while (left <= mid) {
            temp[index++] = array[left++];
        }
        while (right <= end) {
            temp[index++] = array[right++];
        }

        for (index = start; index<= end; index++) {
            array[index] = temp[index];
        }
    }

}
